// 61.旋转链表
package Leetcode_Second_Brush;

public class Solution061 {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode node = head;
        ListNode last = null; // 链表最后一个结点
        
        // 求链表表长，并获取最后一个节点
        int length = 0;
        while (node != null) {
            length++;
            last = node;
            node = node.next;
        }
        if (length == 0)
            return null;
        
        // 重新指向头结点
        node = head; 
        // 如果插入位置为0则直接返回原列表
        if (k % length == 0)
            return head;
        
        // 找到插入位置的上一个节点
        int insetLocation = length - (k % length);
        for (int i = 1; i < insetLocation; i++) {
            node = node.next;
        }
        
        // 调整链表
        ListNode newHead = node.next;
        node.next = null;
        last.next = head;
        return newHead;
    }
}
